P4514 上帝造题的七分钟

题目描述

Info

“第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 $0$ 的 $n \times m$ 矩阵。

第二分钟，L 说，要能修改，于是便有了将左上角为 $(a, b)$ ，右下角为 $(c, d)$ 的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $32$ 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”。

——《上帝造裸题的七分钟》。

所以这个神圣的任务就交给你了。

输入格式

输入数据的第一行为 X n m，代表矩阵大小为 $n \times m$ 。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

L a b c d delta —— 代表将 $(a, b), (c, d)$ 为顶点的矩形区域内的所有数字加上 $d e l t a$ 。
k a b c d —— 代表求 $(a, b), (c, d)$ 为顶点的矩形区域内所有数字的和。

请注意， $k$ 为小写。

$1 \leq n \leq 2048$ ， $1 \leq m \leq 2048$ ， $- 500 \leq d e l t a \leq 500$ ，操作不超过 $2 \times 10^{5}$ 个，保证运算过程中及最终结果均不超过 $32$ 位带符号整数类型的表示范围。

输出格式

针对每个 $k$ 操作，在单独的一行输出答案。

Solution

二维树状数组+二维差分

(待更 $\dots$ )

#define lowbit(x) x&(-x)
int n, m;
int tr1[2100][2100], tr2[2100][2100], tr3[2100][2100], tr4[2100][2100];
void add(int x, int y, int k) {
    for (int i = x;i <= n;i += lowbit(i)) {
        for (int j = y;j <= m;j += lowbit(j)) {
            tr1[i][j] += k;
            tr2[i][j] += x * k;
            tr3[i][j] += y * k;
            tr4[i][j] += x * y * k;
        }
    }
}
void add(int a, int b, int c, int d, int k) {
    add(a, b, k);
    add(c + 1, d + 1, k);
    add(a, d + 1, -k);
    add(c + 1, b, -k);
}
int sum(int x, int y) {
    int ans = 0;
    for (int i = x;i;i -= lowbit(i)) {
        for (int j = y;j;j -= lowbit(j)) {
            ans += (x + 1) * (y + 1) * tr1[i][j] - (y + 1) * tr2[i][j] - (x + 1) * tr3[i][j] + tr4[i][j];
        }
    }
    return ans;
}
int query(int a, int b, int c, int d) {
    return sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1);
}
void solve() {
    char op;cin >> op >> n >> m;
    while (cin >> op) {
        if (op == 'L') {
            int a, b, c, d, delta;cin >> a >> b >> c >> d >> delta;
            add(a, b, c, d, delta);
        } else {
            int a, b, c, d;cin >> a >> b >> c >> d;
            cout << query(a, b, c, d) << '\n';
        }
    }
}